package codingforgreat.lchot150;

//二叉搜索树中继后续
public class Lc285 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public int func(TreeNode root,int val){
        //val 的后继
        TreeNode cur = root;
        boolean isval = false;
        TreeNode MR = null;
        while(cur != null){
            MR = cur.left;
            if(MR != null){
                while (MR.right != null && MR.right != cur){
                    MR = MR.right;
                }
                if(MR.right == cur){
                    //第二次
                    if(isval){
                        return cur.val;
                    }
                    if(cur.val > val){
                        isval = true;
                    }
                    MR.right = null;
                }else{
                    MR.right = cur;
                    cur = cur.left;
                    continue;
                }
            }else{
                if(isval){
                    return cur.val;
                }
                if(cur.val > val){
                    isval = true;
                }
            }
            cur = cur.right;
        }
        return -1;
    }
}
